Multimedia authentication is a technology to check authenticity and integrity of multimedia signals. It is often desirable to localize tampered pixels or samples for a tampered signal so unmodified parts can still be used. Technologies to fulfill this goal have been actively studied in recent years. A class of proposed technologies, called complete or hard authentication, is to detect any modifications to a multimedia signal. Hard authentication technologies can be classified into pixel-wise schemes and block-wise schemes. A pixel-wise scheme is designed to localize tampered pixels (or samples that are implied by “pixels” in the following without explicit reference for audio signals) in additional to verify authenticity for the whole signal. A block-wise scheme, on the other hand, is designed to localize tampered blocks. A block-wise scheme is securer in general than a pixel-wise one, but has much coarser tamper localization capability. Details on proposed authentication technologies can be found in [1][2].
One of the first pixel-wise authentication schemes was the fragile watermarking scheme proposed by Yeung and Mintzer (Y-M scheme) [3][4]. For grayscale images, the Y-M scheme applies a secret binary function to map the value of each pixel, perturbed if necessary, to a preset logo bit. The scheme is able to localize a single tampered pixel. Its vulnerabilities under various circumstances were reported in [5]-[9], and fixes in [10]-[13]. A typical fix is to introduce neighborhood dependency in mapping a pixel to a logo bit, such as the scheme proposed in [10]. These fixes can thwart the attacks reported in [5]-[9], but, as pointed out by Fridrich in [14], are vulnerable to oracle attacks if the pixel scan order, i.e., the order that pixels are watermarked in the embedding process, is public, and if the oracle returns locations of the detected tampered pixels. Fridrich attributed this new vulnerability to the inherent sequential nature in modifying pixels during the watermarking process in a pixel-wise scheme, and believed that no pixel-wise schemes could fix this vulnerability. She turned attention to develop a block-wise scheme in [14] which does not suffer from any of the aforementioned vulnerabilities for pixel-wise schemes. Unfortunately, a block-wise scheme greatly reduces the tampering localization capability. A tampered pixel can no longer to be identified.
Moreover, all existing pixel-wise schemes, regardless of whether pixel scan order is public or private/secret, are vulnerable under oracle attacks. Such schemes typically assert that an image is authentic if no pixel is found tampered. In such schemes, the authenticity of a pixel is checked by applying a many-to-one mapping function to map the value of each pixel to a bit which is compared against a logo bit. Pixels are watermarked sequentially, one pixel at a time. These features enable pixel-wise schemes with good perceptual quality, but are also exploited by oracle attacks. (See also, “Efficient Oracle Attacks on Yeung-Mintzer and Variant Authentication Schemes”, Jinhai Wu et al, June 2004, which is incorporated by reference).
In view of the above, block-wise image authentication schemes are typically considered to be the only viable solution. One such solution is a blockwise authentication scheme which can localize tampered blocks rather than a single pixel—for security reasons, the size of a block is generally 128 pixels or larger.
Although block-wise schemes are generally considered to be the only image authentication techniques that are not vulnerable to oracle attacks, many applications would benefit from an authentication scheme that has a finer tamper localization capability. Unfortunately, as described above, existing pixel-wise schemes, regardless of whether pixel scan order is public or secret, are vulnerable under oracle attacks.